
        <html>
			<head>
			     <title>聊一聊随机数安全 - iv4n</title>
				 <meta http-equiv="content-type" content="text/html; charset=UTF-8">
			</head>
			<body>
				<h1>原文地址:<a href="http://drops.wooyun.org/tips/16053">http://drops.wooyun.org/tips/16053</a></h1>
				
      <p>
        <h1>0x00 简介</h1>

<hr />

<p>和朋友聊到一个比较有意思的现象，在最近两年的校招面试中，大部分同学连一点基础的密码学知识都没有， 即便是有一些渗透功底的同学。</p>

<p>所以这里想和大家聊一些简单的密码学基础知识，不涉及算法实现，更多的是和常见的漏洞场景联系起来，让问题更容易理解，有点抛砖引玉的意思。</p>

<p>本文主要聊一下随机数，随机数其实是非常广泛的，可以说也是密码技术的基础。</p>

<p>对随机数的使用不当很可能会导致一些比较严重的安全问题， 并且这些安全问题通常会比较隐蔽。</p>

<!--more-->

<h1>0x01 随机数</h1>

<hr />

<h3>概述</h3>

<p>随机数在计算机应用中使用的比较广泛，最为熟知的便是在密码学中的应用。本文主要是讲解随机数使用导致的一些Web安全风。</p>

<p>我们先简单了解一下随机数</p>

<p><img src="http://static.wooyun.org//drops/20160522/2016052214505392367pic2.jpg" alt="p2" /></p>

<p><img src="http://static.wooyun.org//drops/20160522/2016052214505430361pic3.jpg" alt="p3" /></p>

<h4>分类</h4>

<p>随机数分为真随机数和伪随机数，我们程序使用的基本都是伪随机数，其中伪随机又分为强伪随机数和弱伪随机数。</p>

<ol>
<li><strong>真随机数</strong>，通过物理实验得出，比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等</li>
<li><strong>伪随机数</strong>，通过一定算法和种子得出。软件实现的是伪随机数 

<ol>
<li><strong>强伪随机数</strong>，难以预测的随机数</li>
<li><strong>弱伪随机数</strong>，易于预测的随机数</li>
</ol></li>
</ol>

<h4>特性</h4>

<p>随机数有3个特性，具体如下：</p>

<ol>
<li><strong>随机性</strong>：不存在统计学偏差，是完全杂乱的数列</li>
<li><strong>不可预测性</strong>：不能从过去的数列推测出下一个出现的数</li>
<li><strong>不可重现性</strong>：除非将数列本身保存下来，否则不能重现相同的数列</li>
</ol>

<p>随机数的特性和随机数的分类有一定的关系，比如，弱伪随机数只需要满足随机性即可，而强位随机数需要满足随机性和不可预测性，真随机数则需要同时满足3个特性。</p>

<p>引发安全问题的关键点在于不可预测性。</p>

<h3>伪随机数的生成</h3>

<p>我们平常软件和应用实现的都是伪随机数，所以本文的重点也就是伪随机数。</p>

<p>伪随机数的生成实现一般是<strong>算法+种子</strong>。</p>

<p>具体的伪随机数生成器PRNG一般有：</p>

<ol>
<li>线性同余法</li>
<li>单向散列函数法</li>
<li>密码法</li>
<li>ANSI X9.17</li>
</ol>

<p>比较常用的一般是线性同余法，比如我们熟知的C语言的rand库和Java的java.util.Random类，都采用了线性同余法生成随机数。</p>

<h3>应用场景</h3>

<p>随机数的应用场景比较广泛，以下是随机数常见的应用场景：</p>

<ul>
<li>验证码生成</li>
<li>抽奖活动</li>
<li>UUID生成</li>
<li>SessionID生成</li>
<li>Token生成 

<ul>
<li>CSRF Token</li>
<li>找回密码Token</li>
</ul></li>
<li>游戏（随机元素的生成） 

<ul>
<li>洗牌</li>
<li>俄罗斯方块出现特定形状的序列</li>
<li>游戏爆装备</li>
</ul></li>
<li>密码应用场景 

<ul>
<li>生成密钥：对称密码，消息认证</li>
<li>生成密钥对：公钥密码，数字签名</li>
<li>生成IV： 用于分组密码的CBC，CFB和OFB模式</li>
<li>生成nonce: 用于防御重放攻击; 分组密码的CTR模式</li>
<li>生成盐：用于基于口令的密码PBE等</li>
</ul></li>
</ul>

<h1>0x02 随机数的安全性</h1>

<hr />

<p>相比其他密码技术，随机数很少受到关注，但随机数在密码技术和计算机应用中是非常重要的，不正确的使用随机数会导致一系列的安全问题。</p>

<h3>随机数的安全风险</h3>

<p>随机数导致的安全问题一般有两种</p>

<ol>
<li>应该使用随机数，开发者并<strong>没有使用随机数</strong>；</li>
<li>应该使用强伪随机数，开发者<strong>使用了弱伪随机数</strong>。</li>
</ol>

<p>第一种情况，简单来讲，就是我们需要一个随机数，但是开发者没有使用随机数，而是指定了一个常量。当然，很多人会义愤填膺的说，sb才会不用随机数。但是，请不要忽略我朝还是有很多的。主要有两个场景：</p>

<p>开发者缺乏基础常识不知道要用随机数；</p>

<p>一些应用场景和框架，接口文档不完善或者开发者没有仔细阅读等原因。</p>

<p>比如找回密码的token，需要一个伪随机数，很多业务直接根据用户名生成token；</p>

<p>比如OAuth2.0中需要第三方传递一个state参数作为CSRF Token防止CSRF攻击，很多开发者根本不使用这个参数，或者是传入一个固定的值。由于认证方无法对这个值进行业务层面有效性的校验，导致了OAuth的CSRF攻击。</p>

<p>第二种情况，主要区别就在于伪随机数的强弱了，大部分（所有？）语言的API文档中的基础库（常用库）中的random库都是弱伪随机，很多开发自然就直接使用。但是，最重要也最致命的是，<strong>弱伪随机数是不能用于密码技术的</strong>。</p>

<p>还是第一种情况中的找回密码场景，关于token的生成， 很多开发使用了时间戳作为随机数（md5(时间戳)，md5(时间戳+用户名)），但是由于时间戳是可以预测的，很容易就被猜解。<strong>不可预测性是区分弱伪随机数和强伪随机数的关键指标</strong>。</p>

<p>当然，除了以上两种情况，还有一些比较特别的情况，通常情况下比较少见，但是也不排除：</p>

<ol>
<li>种子的泄露，算法很多时候是公开的，如果种子泄露了，相当于随机数已经泄露了；</li>
<li>随机数池不足。这个严格来说也属于弱伪随机数，因为随机数池不足其实也导致了随机数是可预测的，攻击者可以直接暴力破解。</li>
</ol>

<h3>漏洞实例</h3>

<p>wooyun上有很多漏洞，还蛮有意思的，都是和随机数有关的。</p>

<p>PS：个人实力有限，以下实例基本都来自wooyun漏洞实例，在这里谢谢各位大牛，如有侵权，请联系删除。</p>

<p><strong>1.应该使用随机数而未使用随机数</strong></p>

<p>Oauth2.0的这个问题特别经典，除了wooyun实例列出来的，其实很多厂商都有这个问题。</p>

<p>Oauth2.0中state参数要求第三方应用的开发者传入一个CSRF Token（随机数），如果没有传入或者传入的不是随机数，会导致CSRF登陆任意帐号：</p>

<ol>
<li><a href="http://www.wooyun.org/bugs/wooyun-2015-012402">唯品会账号相关漏洞可通过csrf登录任意账号</a></li>
<li><a href="http://www.wooyun.org/bugs/wooyun-2014-054785">人人网-百度OAuth 2.0 redirect_uir CSRF 漏洞</a></li>
</ol>

<p><strong>2.使用弱伪随机数</strong></p>

<p><strong>1) 密码取回</strong></p>

<p>很多密码找回的场景，会发送给用户邮件一个url，中间包含一个token，这个token如果猜测，那么就可以找回其他用户的密码。</p>

<p>1.Shopex 4.8.5密码取回处新生成密码可预测漏洞</p>

<p>直接使用了时间函数microtime()作为随机数，然后获取MD5的前6位。</p>

<pre><code>#!php
substr(md5(print_r(microtime(),true)),0,6);
</code></pre>

<p>PHP 中microtime()的值除了当前服务器的秒数外，还有微秒数，微妙数的变化范围在0.000000 -- 0.999999 之间，一般来说，服务器的时间可以通过HTTP返回头的DATE字段来获取，因此我们只需要遍历这1000000可能值即可。但我们要使用暴力破解的方式发起1000000次网络请求的话，网络请求数也会非常之大。可是shopex非常贴心的在生成密码前再次将microtime() 输出了一次：</p>

<pre><code>#!php
$messenger = &amp;$this-&gt;system-&gt;loadModel('system/messenger');echo microtime()."&lt;br/&gt;";
</code></pre>

<p>2.<a href="http://www.wooyun.org/bugs/wooyun-2010-08333">奇虎360任意用户密码修改</a></p>

<p>直接是MD5(unix时间戳)</p>

<p>3.<a href="http://www.wooyun.org/bugs/wooyun-2013-025948">涂鸦王国弱随机数导致任意用户劫持漏洞，附测试POC</a></p>

<p>关于找回密码随机数的问题强烈建议大家参考拓哥的11年的文章<a href="http://www.inbreak.net/archives/349">《利用系统时间可预测破解java随机数| 空虚浪子心的灵魂》</a></p>

<p><strong>2) 其他随机数验证场景</strong></p>

<ul>
<li><a href="http://www.wooyun.org/bugs/wooyun-2015-0160093">CmsEasy最新版暴力注入(加解密缺陷/绕过防注入)</a></li>
</ul>

<p>弱伪随机数被绕过</p>

<ul>
<li><a href="http://www.wooyun.org/bugs/wooyun-2013-020759">Espcms v5.6 暴力注入</a></li>
</ul>

<p>Espcms中一处SQL注入漏洞的利用，利用时发现espcms对传值有加密并且随机key,但是这是一个随机数池固定的弱伪随机数，可以被攻击者遍历绕过</p>

<ul>
<li><a href="http://www.wooyun.org/bugs/wooyun-2014-06239">Destoon B2B 2014-05-21最新版绕过全局防御暴力注入（官方Demo可重现）</a></li>
</ul>

<p>使用了microtime()作为随机数，可以被预测暴力破解</p>

<p>Android 4.4之前版本的Java加密架构(JCA)中使用的Apache Harmony 6.0M3及其之前版本的SecureRandom实现存在安全漏洞，具体位于<code>classlib/modules/security/src/main/java/common/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java</code></p>

<p>类的engineNextBytes函数里，当用户没有提供用于产生随机数的种子时，程序不能正确调整偏移量，导致PRNG生成随机序列的过程可被预测。</p>

<ul>
<li><a href="http://drops.wooyun.org/papers/5164">Android SecureRandom漏洞详解</a></li>
</ul>

<h3>安全建议</h3>

<p>上面讲的随机数基础和漏洞实例更偏重是给攻击者一些思路，这里更多的是一些防御和预防的建议。</p>

<ol>
<li>业务场景需要使用随机数，一定要使用随机数，比如Token的生成；</li>
<li>随机数要足够长，避免暴力破解；</li>
<li>保证不同用处的随机数使用不同的种子</li>
<li><strong>对安全性要求高的随机数（如密码技术相关）禁止使用的弱伪随机数：</strong> 

<ol>
<li><strong>不要使用时间函数作为随机数（很多程序员喜欢用时间戳）</strong> Java：system.currenttimemillis() php：microtime()</li>
<li>不要使用弱伪随机数生成器 Java: java.util.Random PHP: rand() 范围很小，32767 PHP: mt_rand() 存在缺陷</li>
</ol></li>
<li>强伪随机数CSPRNG（安全可靠的伪随机数生成器(Cryptographically Secure Pseudo-Random Number Generator）的各种参考</li>
</ol>

<table>
<thead>
<tr>
  <th>Platform</th>
  <th>CSPRNG</th>
</tr>
</thead>
<tbody>
<tr>
  <td>PHP</td>
  <td>mcrypt&#95;create&#95;iv, openssl&#95;random&#95;pseudo_bytes</td>
</tr>
<tr>
  <td>Java</td>
  <td>java.security.SecureRandom</td>
</tr>
<tr>
  <td>Dot NET (C#, VB)</td>
  <td>System.Security.Cryptography.RNGCryptoServiceProvider</td>
</tr>
<tr>
  <td>Ruby</td>
  <td>SecureRandom</td>
</tr>
<tr>
  <td>Python</td>
  <td>os.urandom</td>
</tr>
<tr>
  <td>Perl</td>
  <td>Math::Random::Secure</td>
</tr>
<tr>
  <td>C/C++ (Windows API)</td>
  <td>CryptGenRandom</td>
</tr>
<tr>
  <td>Any language on GNU/Linux or Unix</td>
  <td>Read from /dev/random or /dev/urandom</td>
</tr>
</tbody>
</table>

<p>6.强伪随机数生成（不建议开发自己实现）</p>

<p>产生高强度的随机数，有两个重要的因素：种子和算法。算法是可以有很多的，通常如何选择种子是非常关键的因素。 如Random，它的种子是System.currentTimeMillis()，所以它的随机数都是可预测的， 是弱伪随机数。</p>

<p>强伪随机数的生成思路：收集计算机的各种信息，键盘输入时间，内存使用状态，硬盘空闲空间，IO延时，进程数量，线程数量等信息，CPU时钟，来得到一个近似随机的种子，主要是达到不可预测性。</p>

<h1>0x03 附</h1>

<hr />

<p>参考资料：</p>

<ul>
<li><a href="http://www.inbreak.net/archives/349">http://www.inbreak.net/archives/349</a></li>
<li><a href="http://drops.wooyun.org/papers/1066">http://drops.wooyun.org/papers/1066</a></li>
<li>《白帽子讲Web安全》</li>
<li>《图解密码技术》</li>
</ul>      </p>
    
			</body>
		</html>
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          